// m

// 给定浮点数x和整数n，计算x的n次方

// 思路：
// 常规方法是将x累计乘以n次得出结果，时间复杂度为O(n)
// 使用快速幂可以减少时间复杂度
// 低纬度的幂计算来得到高纬度的幂计算结果，这样递归求解的时间复杂度为O(logn)，并且递归也可以转为递推来做


function mPow(x, n) {
    if (x === 0) {
        return 0
    }
    let res = 1
    if (n < 0) {
        x = 1 / x
        n = Math.abs(n)
    }
    while (n) {
        //判断n的二进制最后一位是否是1， 如果是1则将结果乘以x
        if (n & 1) {
            res *= x
        }
        //进行无符号右移1位，此处不能使用有符号右移（>>）
        //当n为-2^31转换成正数时的二进制位“10000000000000000000000000000000” , 
        // 如果采用有符号右移时会取最左侧的数当符号即（1），所以返回的结果是 - 1073741824
        x *= x
        n >>>= 1
    }
    return res
}


console.log(mPow(3, 9));
